package LinkedList;

/**
 *  题目 ：展开多级双向链表
 *  多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。
 *  这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
 *
 * 给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。
 *
 */
public class OfferP28 {
    /**
     * 核心思想 ：递归
     * 即，由于存在子链表，所以我们需要递归对整条多级双向链表进行展开
     * @param head
     * @return
     * 返回的是 :链表的尾节点
     */
    public Node flatten(Node head) {
        // 调用方法
        flattenGetTail(head);
        return head;
    }
    public Node flattenGetTail(Node head) {
        Node node = head;
        // 由于此方法需要返回尾节点，所以我们通过设置Node tail来随时记录尾节点
        Node tail = null;
        // 即，当链表
        while(node != null){
            // next节点可能为null值，若是next节点为null值的话，不能使得其指向前一个节点
            Node next = node.next;
            // 当存在子链表的情况下，需要进行递归拼接子链表
            if(node.child != null){
                Node child = node.child;
                /**
                 *  思考 : 为何此处需要将node.child置为null值；
                 *  即，若是不将node.child值置为null的话，会认为其依然为多级双向链表
                 */
                node.child = null;
                // 前一个节点与子链表拼接成双向链表（即，node节点与node.child节点相互指向）
                node.next = child;
                child.prev = node;
                // 递归将多级子链表拼接到双向链表
                Node childTail = flattenGetTail(child);
                // 后一个节点与子链表拼接成双向链表（即，node.next节点与childTail节点相互指向）
                childTail.next = next;
                if(next != null) {
                    next.prev = childTail;
                }
                // 将所要返回的尾节点设置为子链表的tail节点
                tail = childTail;
            }
            else {
                tail = node;
            }
            node = next;
        }
        System.out.println(tail.val);
        return tail;
    }
    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;

    }
}



